import random
class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.arr = []
        self.hash = {}

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.hash:
            return False
        else:
            self.arr.append(val)
            self.hash[val] = len(self.arr) - 1
            return True


    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.hash:
            index = self.hash.pop(val)
            self.arr[index] = None
            return True
        else:
            return False


    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """

        while True:
            while len(self.arr) and self.arr[-1] is None:
                self.arr.pop(-1)
            ran = random.randint(0, len(self.arr) - 1)
            if self.arr[ran] is None:
                self.arr[ran] = self.arr[-1]
                self.hash[self.arr[ran]] = ran
                self.arr.pop(-1)
            else:
                return self.arr[ran]